package huawei.dfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/clone-graph/
 */
public class J133 {
    Map<Node,Node> map=new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node==null){
            return null;
        }
        Node copy = new Node(node.val);
        map.put(node,copy);
        for (Node linjie : node.neighbors) {
            if(map.containsKey(linjie)){
                copy.neighbors.add(map.get(linjie));
            }else {
                Node linjieCopy=cloneGraph(linjie);
                copy.neighbors.add(linjieCopy);
            }
        }
        return copy;
    }
}
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}